/LMAR=0/XLINE=3/FONT#0=BAXL30[FNT,CLT]/FONT#1=BAXM30/FONT#2=BAXB30[FNT,CLT]/FONT#5=GACS25/FONT#3=SUB/FONT#4=SUP/FONT#7=SYMB30[FNT,CLT]
␈↓ ↓H␈↓␈↓ ∧+COMPUTER SCIENCE DEPARTMENT␈↓ ↓H␈↓␈↓ εH␈↓ 91
␈↓ ↓H␈↓␈↓ ¬πSTANFORD UNIVERSITY

␈↓ ↓H␈↓CS206  ␈↓ βZCOMPUTING WITH SYMBOLIC EXPRESSIONS  ␈↓ 
0FALL 1978

␈↓ ↓H␈↓␈↓ ε↔FINAL
␈↓ ↓H␈↓␈↓ ¬tDecember 14

␈↓ ↓H␈↓α␈↓ ∧OThis test is open book and open note

␈↓ ↓H␈↓α␈↓ ¬iProgramming


␈↓ ↓H␈↓        Write␈α∂LISP␈α⊂programs␈α∂for␈α∂each␈α⊂of␈α∂the␈α⊂functions␈α∂described␈α∂below.␈α⊂ The␈α∂functions␈α⊂can␈α∂be
␈↓ ↓H␈↓written␈α⊂in␈α∂either␈α⊂internal␈α∂or␈α⊂external␈α∂notation.␈α⊂ Assume␈α∂a␈α⊂reasonable␈α∂number␈α⊂of␈α⊂functions␈α∂are
␈↓ ↓H␈↓system␈α∂defined␈α∂(e.g.␈α∂APPEND,␈α∂REVERSE,␈α∂PLUS,␈α⊂etc.)␈α∂but␈α∂when␈α∂in␈α∂doubt,␈α∂write␈α⊂the␈α∂function
␈↓ ↓H␈↓yourself.

␈↓ ↓H␈↓1)(16␈αpts.)␈αWrite␈αa␈αprogram␈α␈↓↓variants[n]␈↓␈αwhich␈αyields␈αa␈αlist␈αof␈αall␈αthe␈αS-expressions␈αin␈αNIL␈αof␈αsize
␈↓ ↓H␈↓␈↓ α(␈↓↓n.␈↓ The following is a set of i/o pairs satisfying the function definition.
␈↓ ↓H␈↓␈↓↓variant[␈↓¬0␈↓↓] = ()␈↓
␈↓ ↓H␈↓␈↓↓variant[␈↓¬1␈↓↓] = (NIL)␈↓
␈↓ ↓H␈↓␈↓↓variant[␈↓¬2␈↓↓] = ((NIL. NIL))␈↓
␈↓ ↓H␈↓␈↓↓variant[␈↓¬3␈↓↓] = ( (NIL .(NIL. NIL)) ((NIL . NIL) . NIL))␈↓

␈↓ ↓H␈↓2)␈α(16␈αpts.)The␈αfollowing␈αis␈αa␈αprogram␈αto␈αcompute␈αthe␈αintersection␈αof␈α␈↓↓u␈↓␈αand␈α␈↓↓v␈↓␈αwhere␈αboth␈αare␈αlists
␈↓ ↓H␈↓␈↓ α(of␈α
atoms.␈α
 Its␈αrunning␈α
time␈α
in␈α
the␈αworst␈α
case␈α
is␈α␈↓↓length[u]*length[v].␈↓␈α
Rewrite␈α
a␈α
version␈αof
␈↓ ↓H␈↓␈↓ α(␈↓↓intersection␈↓␈α⊂which␈α⊂runs␈α∂in␈α⊂time␈α⊂␈↓↓length[u]+length[v].␈↓␈α∂ Hint:␈α⊂Use␈α⊂the␈α∂property␈α⊂list␈α⊂of␈α∂the
␈↓ ↓H␈↓␈↓ α(atoms involved.

␈↓ ↓H␈↓↓      intersection[u,v] ← 
␈↓ ↓H␈↓↓              ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓
␈↓ ↓H␈↓↓              ␈↓αelse␈↓↓if member[␈↓αa|␈↓↓u,v] then [␈↓αa|␈↓↓u] . intersection[␈↓αd|␈↓↓u,v]
␈↓ ↓H␈↓↓              ␈↓αelse␈↓↓ intersection[␈↓αd|␈↓↓u,v]


␈↓ ↓H␈↓Why would this not work if ␈↓↓u␈↓ and ␈↓↓v␈↓ were not lists of atoms.

␈↓ ↓H␈↓3)␈α∂(16␈α∂pts.)Let␈α∂␈↓↓x␈↓␈α∂be␈α∂a␈α∂possibly␈α∞re-entrant␈α∂list␈α∂structure.␈α∂ Write␈α∂the␈α∂LISP␈α∂function␈α∂␈↓↓count[x]␈↓␈α∞that
␈↓ ↓H␈↓␈↓ α(gives␈α
the␈α
number␈αof␈α
distinct␈α
vertices␈α
in␈αx.␈α
 Hint:␈α
Use␈α
a␈αvariable␈α
␈↓↓u␈↓␈α
that␈α
lists␈αvertices␈α
already
␈↓ ↓H␈↓␈↓ α(seen.

␈↓ ↓H␈↓4)␈α
(16␈α
pts.)Write␈α
a␈α
program␈α
using␈α
RPLACA␈α
and␈α
RPLACD␈α
which␈α
yields␈α
a␈α
re-entrant␈α
list␈α
structure
␈↓ ↓H␈↓␈↓ α(corresponding␈αto␈αa␈αgraph␈αin␈αthe␈αnotation␈αdescribed␈αin␈αthe␈αnotes.␈α Thus␈α((A␈αB␈αC)␈α(B␈αA␈αD)
␈↓ ↓H␈↓␈↓ α((C D E) (D B E)) becomes
␈↓ ↓H␈↓Note␈α
that␈α
many␈α
of␈α
the␈α∞atoms␈α
in␈α
the␈α
non-re-entrant␈α
list␈α∞are␈α
representd␈α
by␈α
lists␈α
in␈α∞the␈α
re-entrant␈↓ ↓H␈↓␈↓ εH␈↓ 92
␈↓ ↓H␈↓␈↓ α(list.␈α∞ You␈α
may␈α∞use␈α
notations␈α∞like␈α
ad␈α∞x␈α
←␈α∞y␈α
instead␈α∞of␈α
(RPLACA␈α∞(CDR␈α
x)␈α∞y).␈α∞ This␈α
also
␈↓ ↓H␈↓␈↓ α(applies for RPLACD.

␈↓ ↓H␈↓α␈↓ ε∩Proving


␈↓ ↓H␈↓5)␈α     (16␈αpts.)Given␈αthe␈αfollowing␈αfunction␈αdescriptions␈αprove␈αthe␈αrequired␈αtheorem.␈α Be␈αexplicit
␈↓ ↓H␈↓and␈α∩rigorous␈α∩in␈α∩recording␈α∩your␈α∩proof.␈α∩ Justify␈α∩each␈α∩individual␈α∩step␈α∩(i.e.␈α∪function␈α∩expansion,
␈↓ ↓H␈↓induction␈αhypothesis,␈αetc.).␈α The␈αonly␈αtheorems␈αyou␈αmay␈αassume␈αhave␈αbeen␈αpreviously␈αproved␈αare
␈↓ ↓H␈↓the␈α
associativity␈α
of␈α
append␈αand␈α
that␈α
NIL␈α
is␈αthe␈α
identity␈α
for␈α
append␈α
(on␈αeither␈α
side).␈α
 If␈α
you␈αneed␈α
a
␈↓ ↓H␈↓lemma, prove it.

␈↓ ↓H␈↓↓      member[x,u] ← 
␈↓ ↓H␈↓↓              ¬ ␈↓αn|␈↓↓u ∧ [x = [␈↓αa|␈↓↓u] ∨ member[x, ␈↓αd|␈↓↓u]]

␈↓ ↓H␈↓↓      append[u,v] ← 
␈↓ ↓H␈↓↓              ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ v
␈↓ ↓H␈↓↓              ␈↓αelse␈↓↓ [␈↓αa|␈↓↓u] . append[␈↓αd|␈↓↓u, v]


␈↓ ↓H␈↓Prove: member[x,append[u,v]] ≡ member[x,u] ∨ member[x,v]






␈↓ ↓H␈↓α␈↓ ¬≡Programming & Proving


␈↓ ↓H␈↓6)␈α
     (20␈αpts.)␈α
Write␈α
programs␈αfor␈α
the␈α
following␈αtwo␈α
functions␈α
and␈αprove␈α
the␈α
required␈αtheorem.
␈↓ ↓H␈↓You can use any lemmas proved in class.  Assume the list ␈↓↓u␈↓ is ordered with no duplications.

␈↓ ↓H␈↓ ␈↓↓insert[n,u]␈↓␈α∞inserts␈α∂the␈α∞number␈α∂␈↓↓n␈↓␈α∞into␈α∞the␈α∂ordered␈α∞list␈α∂␈↓↓u␈↓␈α∞and␈α∞preserves␈α∂the␈α∞ ordered␈α∂and␈α∞non-
␈↓ ↓H␈↓␈↓ α(duplication␈α⊂properties␈α⊂of␈α⊂␈↓↓u.␈↓␈α⊂The␈α⊂following␈α∂is␈α⊂one␈α⊂i/o␈α⊂pair␈α⊂which␈α⊂satisfies␈α⊂the␈α∂function
␈↓ ↓H␈↓␈↓ α(definition.

␈↓ ↓H␈↓␈↓ ∧z␈↓↓insert[␈↓¬(4 (1 2 5))␈↓↓] = (1 2 4 5)␈↓ 

␈↓ ↓H␈↓␈↓↓delete[n,u]␈↓␈α∞deletes␈α∞the␈α∞number␈α∂␈↓↓n␈↓␈α∞from␈α∞the␈α∞ordered␈α∂list␈α∞␈↓↓u.␈↓␈α∞ If␈α∞␈↓↓n␈↓␈α∂is␈α∞not␈α∞ present␈α∞then␈α∂␈↓↓u␈↓␈α∞remains
␈↓ ↓H␈↓␈↓ α(unchanged.  The following is one i/o pair which satisfies the function definition.

␈↓ ↓H␈↓␈↓ ∧w␈↓↓delete[␈↓¬(4 (1 2 4 5))␈↓↓] = (1 2 5)␈↓ 

␈↓ ↓H␈↓Prove: ¬member[n,u] ⊃ [ delete[n,insert[n,u]] = u ]